//出现频率最高的K个数字
class Solution {
public:
    struct cmp
    {
        //建小根堆
        bool operator()(const pair<int,int>p1,const pair<int,int>p2)
        {
            return p1.second>p2.second; 
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) 
    {
        //使用 哈希表记录数字和出现次数
        //然后将它插入到优先级队列里面进行排序
        //需要写一个仿函数辅助排序
        unordered_map<int,int> um;//-> 数字 出现次数
        for(auto e:nums)
        {
            um[e]++;
        }
        priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> q;
        for(auto it=um.begin();it!=um.end();it++)
        {
            q.push(*it);
            if(q.size()>k) q.pop();
        }
        vector<int> res(k);
        for(int i=k-1;i>=0;i--)
        {
            res[i]=q.top().first;
            q.pop();
        }
        return res;
    }
};

//存在重复元素III
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<long long> st;
        for(int i=0;i<nums.size();i++)
        {   
            long long tmp1=(long long)nums[i]-t;       
            long long tmp2=(long long)nums[i]+t;
            //在滑动窗口中, 二分查找满足条件的值
            auto s= st.lower_bound(tmp1);//返回数值大于等于tmp1的迭代器
            if(s!=st.end()&&*s<=tmp2)
            {
                return true;
            }
            st.insert(nums[i]);
            if(i>=k)
            {
                st.erase(nums[i-k]);
            }
        }
       return false;
    }
};
